COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	A useful function for constructing lists will be introduced
C00017 ENDMK
C⊗;
A useful function for constructing lists will be introduced
now.
list[xl; x2 ... xn] generates a list consisting of the values
of the n arguments.  That is: cons[x1; cons[x2 ... cons[xn;NIL]]...]
EXAMPLES
list[A;B] = (A,B)
list [A;B;C] = (A,B,C)
list[cons[A;B];car[(A.B)]] = ((A.B),A)
list [A; list[B;C]] = list [A;(B,C)]
                    = (A, (B,C))

The crutial problems in data structures are the interrela-
tionships between algorithms and the representation which is
chosen.  Once these choices have been made then the rest is easy.
Knuth once remarked that simulation languages should not have
any I/O statements, becaause if you got to the ppoint of running
on a machine then you have done something wrong.  All your ideas
should have been sorted out as you were constructing the model
and describing the algorithms.  He wasn|t quite serious buut the
point should be clear.

This section of notes will exaamine some non-trivial problems
in non-numerical computation (data structures).  We will describe
the problem intuitively, pick an initial representation for the
problem, write the LISP algorithm, and in some cases "tune" the
algorithm by picking "more efficient" data representations.

DIFFERENTIATION

This example will describe a rudimentary differentiation
routine for polynomials in several variables.  First you should
realize that the normal definition of differentiation is
recursive!  The question of differentiation of a sum is thrown
back on the differentiation of each command.  Similar relation- 
ships hold for products, differences, and powers.  As with all
good recursive definitions, there must be some termination
conditions.  What are the termination conditions here?  Differen-
tiation of a variable, say x, w.r.t. to x is defined to be l;
differentiating a constant or a variabble not equal to x with
respect to x gives a result of zero.  It is easy to write recursive
algorithms in LIISP; the only problem is that the domain (and
range) of LISP functions is Sexprs, not the polynomials which
we need.  Problem:  represent arbitrary polynomials as Sexprs.
Though polynominals can be arbitrarily complex, involving plus,
times, minus, powers, etc. their general format is very simple
if they are described in prefix notation (standard mathematical
or functional notation) and we assume that +, *, - and ** are
binary operations.
For example:
      infix                    prefix

     x.z+2y                 +[*[x,z], *[2,y]]
     xyz                    =[x,*[y,z]]
(optional problem:  write BNF equations expressing such a
representation of polynominals)

How does this help us, we still don`t have Sexprs?  First
the operations need to represented as atoms:

      +                     PLUS
       -                    MINUS
      *                      TIMES
      **                    EXPT
How about a representation of variables and constants?  Let
the variables be mapped to their uppercase counterpart, (a
decent atom); and let constants (numbers), be just numbers,
also decent atoms.  Looking ahead to the algorithm, the termina-
tion condition on variables and constants can then just be
given in terms of the predicate, atom.

That is:

if u is a constant or a variable then:

         d u
             =  l if x = u
          dx
                0 otherwise

will translate as :
         atom [u] → [eq[u,x] → l;T → O].

Now finally, how can we represent an arbitrary polynomial
as an sexpr.

Write:

    +[x.y]         as (PLUS, X, Y)
    *[x,y]         as (TIMES, X, Y)
   **[x,y]         as (EXPT, X, Y)
or in general

    f[t1,t2] as (F, translate of t1, traanslate of t2)
for example

    x2 + 2yz + u
can translate to the following prefix notation:

    +[**[x,2], +[*[2,*[y,z]], u]]

(This is messier than it really needs to be because we required
+ and* to be binary)  From this it`s easy to get the sexpr
form:

    PLUS (EXPT, X, 2)  (PLUS (...)
    
Now we can complete the differentiation algorithm.

    d[f + g] = df + dg
       dx      dx   dx

We would see u = f + g as u = (PLUS rep of f, rep of g)
where: cadr u = rep of f
      caddr u = rep of g

Thhe result of differentiation u is to be a new list of three
elements;

     l.  the symbol PLUS
     2.  the effect of diff operating on (the rep. of) f
     3.  the effect of diff operating on (the rep. of) g
Thus another part of the algorithm:

     eq [car[u];PLUS] → list [PLUS; diff[cadr[u]x]
                                    diff[caddr[u];x]]

d[f-g] is very similar.
  dx

d[f*g] is defined to be f* dg + g * df
  dx                       dx       dx

so:  eq[car[u];TIMES] → list[PLUS; list[TIMES; cadr[u];
                        diff [caddr[u];x]];
                                   list[TIMES;caddr[u];
                                   diff [cadr[u];x]]]

Here`s an example
    d[xy + x] H y + 1
        dx

try

   diff [PLUS (TIMES,X,Y) X); X]
=list [PLUS, diff [TIMES X Y) X]; diff [X;X]]

=list [PLUS; list [PLUS; list [TIMES; X; diff [Y;X]];
                         list [TIMES; Y; diff [X;X]]];

            diff [X;X]]

=list [PLUS; list [PLUS; list [TIMES; X ;O];
                         list [TIMES; Y;l]];

            1 ]

=(PLUS, (PLUS (TIMES XO)(TIMES Y 1)) 1)

which can be interpreted ad

    x.O + y.1 + 1 .

Which introduces another set of non-numerical algorithms:
algebraic simplification!

Points to note.

This problem of representation is typical of data structure
algorithms (regardless of what language you use).  That is
once you have decided what the intuitive problem is pick a
representation which makes yyour algorithms clean (then worry
about efficiency.)  In the next set of examples we will see a
 series of representation each becoming more and more "efficient"
and each requiring more "knowledge" being built into the algorithm.

Here's the whole algorithm for differentiation using + and *.

diff[u;x] = [atom [u] → [eq [x,u] → l; T → O];
       eq [car [u]; PLUS] → list [PLUS; diff [cadr [u]; x];
                            diff [caddr [u]; x]]
       eq [car [u]; TIMES] → list [PLUS; list [TIMES; cadr [u];
                           diff [caddr [u]; x]];
                                        list [TIMES; caddr [u];
                           diff [cadr [u]; x]];
T → LOSER]

Algebra of polynomials

Assume we want to perform addition and multiplication
of polynomials and assume that each polynomial is of the
form p1 + p2 + ... + pn where each pi is a product of variables
and constants.  The standard algorithm for addition of
n           m
ε pi with   ε  qj says you can cambine a qj with a pi
i=1        j=1

if the variable parts of these terms are identical.  'n this
case the resulting term has the same variable part but has a
constant part equal to the sum of the constant parts of pi
and qj.

For example if pi is 2x and qu is 3x the sum term is 5x.

First representation
We could use the representation of the differentiation
example.  But since we know the form of polynomials this
representation is more commplex than necessary.

Seccond representation
Using the knowledge of the forms of polynomials, write
ε pi as
     ( (rep of p1), (rep of p2) ...)
and each pi is represented as some listt of its components
(constants and variables)

Is this representation sufficient?  Does it have the 
flexibility we need?  How do we represent the test for 
pi = qj? equal does it.  If they are equal then we build a
new list representing the same variable part but with a constant
part equal to the sum.

Third representation

equal is expensive.  Cann we do better?  That is can we
represent something like 2x2 y3 z better than say
(2, (EXPT, X, 2) (EXPT Y 3) (EXPT Z,1))
First EXPT is really unnecessary
(2, (X 2), (Y 3), (Z l))
Now  if we assume that we know how many variables can ever
appear and then assume that those variables always appear
in the same order in a term then we could write the above as:
( 2, 2, 3, 1 ) assuming x, y, z are the only variables.

Let`s stop for some examples.

      term                 representation
      2xyz                  (2, 1, 1, 1)
      2x2z                  (2, 2, O, 1)
      4z3                   (4, 0, 0, 3)

Now let`s think abouut the structure of the main algorithm.
The algorithm for the sum must compare terms finding like terms
generated a new term, otherwise simply copy the terms.

Fourth representation

When we pick a pi from the first polynomial we would
like to find the corresponding qu with the minimum amount of
searching.  
This can be accomplished if we can order the terms
in the polynomials. So we will assume that there is a maximum
number of digits in the exponents of any term.  For sake of
argument, assume 2 digits then we will represent terms as
follows